package leetcode.Hot100;

import leetcode.TreeNode;

/**
 * @author Cheng Jun
 * Description: 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
 * <p>
 * 提醒一下，二叉搜索树满足下列约束条件：
 * <p>
 * 节点的左子树仅包含键 小于 节点键的节点。
 * 节点的右子树仅包含键 大于 节点键的节点。
 * 左右子树也必须是二叉搜索树。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/10 16:54
 * 二刷 面试题
 */
public class convertBST {

    static int sum = 0;

    public static void main(String[] args) {
        TreeNode a = new TreeNode(5);
        TreeNode b = new TreeNode(6);
        TreeNode c = new TreeNode(3, a, b);
        TreeNode e = new TreeNode(1, null, c);
        convertBST(e);
    }

    // 反序的中序遍历
    static TreeNode convertBST(TreeNode root) {
        if (root != null) {
            //    1
            //  2   3
            //4   5    6
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}
